技术基础

---

算法

算法复杂度速查表

https://www.toutiao.com/i6299320892124037633/

图例

数据结构操作

数组排序算法

堆操作

常见排序算法

1. 冒泡排序

   就是第一个位置上的数与他相邻第二个位置上的数比较，如果比他相邻的数小，则两者交换位置，否则不交换。接着第一个位置上的数与第三个位置上的数比较大小，也是小则交换，一直到和最后一个位置的数比较交换完毕。然后，是下一个循环，就是第二个位置上的数重复上面的比较交换操作，直到把整个数列变成是一个从小到大的有序序列。

2. 插入排序

   从一堆待排序的数列中选出来一个最小值(可以认为第一个数就是已排序的数列)，然后从剩余的带排序的数列中选出来最小值有序放到已排序的数列中，依次操作，直到最后的数列都是一个从小到大的有序数列为止。

3. 选择排序

   从一堆待排序的数列中选出来一个最小值，放到新的数组的第一个位置，继续从剩余的数列中选取最小值放入到数组中，重复上面的步骤，将数字都取出来排成新的有序数列。

4. 希尔排序

   插入排序的一种改进，先比较一定距离的元素成为有序数列，再比较缩小增量距离的元素(可为元素的数量的一半)，一直到比较的是相邻元素的时候，就成为了插入排序。所以希尔排序是插入排序的改进。

5. 堆排序

   1️⃣构造大顶堆 2️⃣交换堆顶和堆底 3️⃣重复前面的步骤升序排列完成

6. 归并排序

   就是将待排序的数列看成是单个的有序的数列，然后进行合并，直到合并成最后的完成整有序的数列。

7. 快速排序

   第一步先从数列中取出一个数作为基准数。

   第二步分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

   第三步再对左右区间重复第二步，直到各区间只有一个数

8. 排序总结

   各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

基础算法

第一名：Union-find 合并操作和查询算法;

第二名：Knuth-Morris-Pratt字符串匹配算法;

第三名：BFPRT 算法;

第四名： Quick sort 快速排序算法 ;

第五名：Floyd-Warshall all-pairs 最短路径算法;

第六名：Gentry’s Fully Homomorphic Encryption Scheme 绅士完全同态加密机制算法;

第七名：Depth First Search、Breadth First Search 深度、广度优先搜索算法;

第八名：Miller-Rabin 作的类似的试验测试算法;

第九名：Binary Search 二分查找算法;

第十名：Huffman coding 霍夫曼编码算法。

规范

提高代码的可读性

1. 代码清晰表达意图

代码的目的是什么，同时会忽略它是如何做的。

我们要遵守的原则是，代码能够让人快速看懂，可以一个月后能快速读懂代码，这是最低的要求啦!

1. 排版规范

程序员的代码排版可是基本功，比如缩进和命名要规范统一，一行不要写太宽，一个函数不要写太长，这些都是最基本的。

1. 注释清晰

通常而言，注释应先于代码存在，而不是编写完代码之后去补注释。

注释应该是说明代码的意图，代码注释贵在精不在多。

1. 解释给别人听

检验代码可读性的最简单的方法之一就是给别人解释代码，通过解释代码，你可以发现理解上的漏洞以及代码的一些细节。

1. 简单就是美

牢记一个代码可读性的法则，即简单就是美，简单可以移动一座大山！

你会发现，保持简单的代码远比写出复杂代码要难得多，但这是值得的。

另外，不要编写讨巧的代码，取巧只会让你过后花更多的时间和精力。

技巧

防御性代码

1. 防御性编程方法：

• 不要信任用户输入

假设你总是会收到你不期望的东西。那么你的方法应该作为一个防御性程序，针对用户输入，或一般进入你系统用户。这就是我们可以预料到意想不到的结果。尽量做到尽可能严格。断言您的输入值是您期望的。

• 最好的防守是进攻

列入白名单而不是黑名单，例如，当验证图像扩展名时，不检查无效的类型，但检查有效的类型，排除所有其余的类型。开源验证库，使您的工作更容易。

最好的防守是一个好的进攻。要谨慎。

• 使用抽象数据库

OWASP十大安全漏洞中的第一个是注入。这意味着有人（很多人在那里）还没有使用安全工具来查询他们的数据库。请使用数据库抽象包和库。

• 不要重新发明轮子

你不使用框架（或微框架）？你喜欢做额外的工作，没有理由，恭喜你！它不仅仅是框架，而且对于新的功能，你可以很容易地使用，经过测试，受到成千上万的开发人员和稳定的信任，而不是仅仅为自己制作的东西。你应该自己创建一个东西的唯一原因是你需要一些不存在或存在但不适合你的需要（性能不佳，缺少的功能等）。

• 不要信任开发人员

防御性编程可以与防御性驾驶的东西相关。在防御驾驶中，我们假设我们周围的每个人都有可能犯错误。所以我们必须小心别人的行为。同样的概念也适用于防御性编程，开发人员不应该信任其他开发人员的代码。也不应该相信我们自己的代码。

在大项目中，许多人参与，我们可以有许多不同的方式来编写和组织代码。这也可能导致混乱，甚至更多的错误。所以我们应该规范编码风格。

• 写入SOLID代码

这是一个（防御）程序员的困难部分，编写代码不吸。这是许多人知道和谈论的事情，但没有人真正关心或投入正确的注意力和努力来实现SOLID代码。

1. 单一职责原则
单一职责原则 (Single Responsibility Principle，SRP) 指出，每个方法或类应当有且仅有
一个改变的理由。这意味着每个方法或类应当做一件事情，或者只有一项职责。在所有的
SOLID 原则中，这是大多数开发人员感到最能完全理解的一条。严格来说，这也可能是违
反最频繁的一条原则了。
 
2. 开放/ 封闭原则
开放/封闭原则(Open/Close Principle，OCP)是指软件(方法、类等)应当开放扩充且关闭
修改。如果觉得它非常类似于继承的OOP 原则，那就对了。
OCP 的要点在于：作为开发人员，别人偶尔会向我们提供基类，偶尔也会为其他开发人
员生成基类框架，供其使用。这些使用者应当仅能使用这些基类，但不能对其进行修改。

这一点是必要的，因为其他使用者也可能依赖于由基类提供的功能。如果允许使用者修改
这些基类，可能会导致连锁反应，不仅会影响到应用程序中的各方面，还会影响到企业内
的应用程序。还有一个问题，使用者有时可能会收到基类的升级版本。使用者在升级之前，
必须找出一种方法用来处理其对该基类先前版本中所做的自定义。
 
3. 里氏替换原则
继承对于OCP，就相当于多态性对于里氏替换原则(Liskov Substitution Principle，LSP)。
LSP 规定：用超类代替应用程序中使用的对象时，应当不会破坏应用程序。这通常也被称
为“契约式设计(design by contract)”。
回想前面的多态性示例，ComputePay 方法使用了Employee 类型的列表，其中Employee
就是基类型(超类型)。Salary、Hourly 和Seasonal 类都是从Employee 继承而来，因此它们
是Employee 的子类型。
根据LSP，即使已经将列表声明为Employee 的列表，也仍然可以用Salary、Hourly
和Seasonal 的具体实例来填充它。因为有了继承，它们都支持Employee 声明的相同契约(公
共的方法集或API)。应用程序可以对该列表进行迭代，并调用那些在列表中各个项目的
Employee 上定义的方法，不需要知道或特别关心它们都是什么类型。如果它们支持契约，
该调用就是合法的。
 
4. 接口分离原则
到目前为止，已经在示例中使用了基于类的继承，但还没有过多地讨论接口。回想一
下，接口就是在代码中定义的契约，而类同意实现这一契约。这份协议要求类来为接口中
定义的所有方法提供实现。至于如何实现方法，则由这个类来决定，只要它遵守契约，支
持接口中的定义即可。接口是.NET 中功能非常强大的功能；它们对继承和多态的支持方式
与类相同。
接口分离原则(Interface Segregation Principle，ISP)规定，不应当强制客户端依赖于其
不使用的接口。例如，银行系统可能有一个用于评估信用申请的服务。为便于讨论，假定
该服务不仅处理有质押信用(车船贷款、抵押)，也处理无质押信用(信用卡、信用证、股票
信用额度)。如果正在开发一个客户端，用于帮助从事汽车代理的金融专员为其客户获得汽
车贷款，则只需要关注汽车贷款的申请即可，无需考虑有关这一服务的任何其他事情。如
果没有 ISP，应用程序可能必须了解其他方法。
尽管乍看起来这并没有什么，但它至少是增加了应用程序的复杂性，因为据以进行开
发的 API 中会有许多方法，远远超出所需要的。这样可能会导致混淆，调用错误的方法还
可能会导致潜在的错误。还有一种可能， API 中未被应用程序用到的部分可能会改变，而
这又会导致对终端的改变。这样，因为没用到、没想用、甚至是根本就不关心的一些功能，
而增加了应用程序的维护成本。这种情况还存在安全风险。该应用程序是专用于汽车贷款
的。如果不道德的开发人员利用这个过于庞大的 API 来允许利用这一申请担保其他类型的
信用，又该怎么办呢？这种问题的严重性就不仅仅是代码瘫痪、不可维护那么简单了。
这一问题的解决方案就是专门针对客户端的需要，为该服务创建几个更小的、更精细
的接口。对于该示例应用程序，专门设计一个针对汽车贷款的接口是比较适当的做法。应
用程序可以用同一实现访问同一个类，但这一次它使用了一个特定的接口，其中仅有实际
服务的一部分方法。这样就降低了复杂性，将应用程序与 API 其他部分的修改隔离开来，
还有助于堵塞安全漏洞。
 
5. 依赖倒置原则
在完美世界里，应用程序的组件之间没有耦合关系或绑定关系。开发人员也能够改变
自己希望改变的任何东西，而不需要担心在应用程序的其他地方出现缺陷，或者“不希望
存在的负面影响”。令人悲伤的是，我们并不是生活在完美世界里。因此，组件需要相互
绑定在一起，或者在某一点耦合，以构成实际应用程序。
依赖倒置原则(Dependency Inversion Principle，DIP)规定：代码应当取决于抽象概念，
而不是具体实现；这些抽象不应当依赖于细节；而细节应当依赖于抽象。类可能依赖于其
他类来执行其工作(Employee 服务可能依赖于数据访问组件向数据存储中保存和检索员工
信息)。但是，它们不应当依赖于该类的特定具体实现，而应当是它的抽象。也就是说，
Employee 服务不知道(或不关心)正在使用哪个具体的数据访问组件——只有它的抽象或代
码契约(或接口)支持那些用于保存和检索员工所需要的方法。
显然，这一概念会大大提高系统的灵活性。如果类只关心它们用于支持特定契约而不
是特定类型的组件，就可以快速而轻松地修改这些低级服务的功能，同时最大限度地降低
对系统其余部分的影响。在第6 章，还会看到如何利用这一概念来模拟这些依赖项，以进
行测试。有时，需要向类中提供这一低级服务的具体实现，以便这个类能够完成自己的工
作。最常见的做法，特别是在.NET 中使用TDD 的开发人员，就是依赖项注入(DI)模式。

养成防御性编码的好习惯

防御性编程是一种编程习惯，是指先预见在什么地方可能会出现问题，然后增加适当的保护措施

当预见的问题出现时，按照预先的设想往下走，如停止执行程序，将用户重指向到一个备份的服务器，或者打开一个诊断问题的调试页

防御性编程技巧

1. 使用好的编码风格和合理的设计

2. 不要仓促地编写代码

   一定要在完成与一个代码段相关的所有任务之后，再进入下一个环节。例如，如果你决定先编写主体部分，再加入错误检查和处理，那么一定要确保这两项工作的完成都遵循章法。

3. 不要相信任何人

— 真正的用户 意外地提供了假的输入，或者错误地操作了程序；

— 恶意的用户 故意造成不好的程序行为；

— 客户端代码 使用错误的参数调用了你的函数，或者提供了不一致的输入；

— 运行环境 没有为程序提供足够的服务；

— 外部程序库 运行失误，不遵从你所依赖的接口协议。

1. 编码的目标是清晰，而不是简洁

   将复杂的代数运算拆分为一系列单独的语句，使逻辑更清晰。

2. 不要让任何人做他们不该做的修补工作

— 在面向对象的语言中，通过将属性设为专用（private）来防止对内部类数据的访问。在C++中，可以考虑使用Cheshire cat/pimpl idiom。（见参考书目Meyers 97）

— 在过程语言中，你仍然可以使用面向对象（oo）的打包概念，将private数据打包在不透明的类型背后，并提供可以操作它们的定义良好的公共函数。

— 将所有变量保持在尽可能小的范围内。不到万不得已，不要声明全局变量。如果变量可以声明为函数内的局部变量，就不要在文件范围上声明。如果变量可以声明为循环体内的局部变量，就不要在函数范围上声明。

1. 编译时打开所有警告开关

   如果你的代码产生了任何的警告信息，立即修正代码，让编译器的报错声停下来。

   关键概念 编译器的警告可以捕捉到许多愚蠢的编码错误。在任何情况下都启用它们。确保你的代码可以安安静静地完成编译。

2. 使用静态分析工具

   编辑器警告是对代码的一次有限的静态分析（即在程序运行之前执行的代码检查）的结果。

   还有许多独立的静态分析工具可供使用，如用于Ｃ语言的lint（以及更多新出的衍生工具）和用于.NET汇编程序的FxCop。你的日常编程工作，应该包括使用这些工具来检查你的代码。它们会比你的编译器挑出更多的错误。

3. 使用安全的数据结构

   如果你做不到，那么就安全地使用危险的数据结构。

   最常见的安全隐患大概是由缓冲溢出引起的。缓冲溢出是由于不正确地使用固定大小的数据结构而造成的。如果你的代码在没有检查一个缓冲的大小之前就写入这个缓冲，那么写入的内容总是有可能会超过缓冲的末尾的。

4. 检查所有的返回值

   如果一个函数返回一个值，它这样做肯定是有理由的。检查这个返回值。如果返回值是一个错误代码，你就必须辨别这个代码并处理所有的错误。不要让错误悄无声息地侵入你的程序；忍受错误会导致不可预知的行为。

5. 审慎地处理内存（和其他宝贵的资源）

   对于在执行期间所获取的任何资源，必须彻底释放。内存是这类资源最常提到的一个例子，但并不是唯一的一个。文件和线程锁也是我们必须小心使用的宝贵资源。做一个好的“管家”。

1. 在声明位置初始化所有变量

   这是一个显而易见的问题。如果你初始化了每个变量，它们的用途就会是明确的。依靠像“如果我不初始化它，我就不关心初始值”的经验主义是不安全的。代码将会发展。未初始化的值以后可能随时都会变成问题。

2. 尽可能推迟一些声明变量
   尽可能推迟一些声明变量，可以使变量的声明位置与使用它的位置尽量接近，从而防止它干扰代码的其他部分。这样做也使得使用变量的代码更加清晰。你不再需要到处寻找变量的类型和初始化，在附近声明使这些都变得非常明显。

不要在多个地方重用同一个临时变量，即使每次使用都是在逻辑上相互分离的区域中进行的。变量重用会使以后对代码重新完善的工作变得异常复杂。每次都创建一个新的变量——编译器会解决任何有关效率的问题。

1. 使用标准语言工具

   明确地定义你正在使用的是哪个语言版本。除非你的项目要求你（最好是有一个好的理由），否则不要将命运交给编译器，或者对该语言的任何非标准的扩展。如果该语言的某个领域还没有定义，就不要依赖你所使用的特定编译器的行为（例如，不要依赖你的C编译器将char作为有符号的值对待，因为其他的编译器并不是这样的）。这样做会产生非常脆弱的代码。当你更新了编译器之后，会发生什么？一位新的程序员加入到开发团队中，如果他不理解那些扩展，会发生什么？依赖于特定编译器的个别行为，将导致以后难以发现的错误。

2. 使用好的诊断信息日志工具

   有很多诊断信息日志系统可以帮助实现这种功能。这些系统中很多都可以使诊断信息在不需要的时候不带来任何开销；可以有选择地使它们不参加编译。

3. 审慎地进行强制转换

   如果你真的想使用强制转换，就必须对之深思熟虑。你所告诉编译器的是：“忘记类型检查吧：我知道这个变量是什么，而你并不知道。”你在类型系统中撕开了一个大洞，并直接穿越过去。这样做很不可靠。如果你犯了任何一种错误，编译器将只会静静地坐在那里小声嘀咕道：“我告诉过你的。”如果你很幸运（例如使用Java或C#），运行时可能会抛出异常以让你了解发生了错误，但这完全依赖于你要进行的是什么转换。

4. 细则

   低级别防御性代码的编写技巧有很多。这些技巧是日常编程工作的组成部分，包含在对现实世界的一种健康的怀疑当中。下面的几条细则值得考虑：

• 提供默认的行为

  大多数语言都提供了一条switch语句；这些语言都将碰到default case的执行情况。如果default case是错误的，在代码中将错误情况明示出来。如果一切都正常，也要在代码中明示顺利执行的情况，只有这样维护代码的程序员才会理解程序的执行情况。

  同样地，如果你要编写一条不带else子句的if语句，停下来想一想，你是否应该处理这个逻辑上的默认情况。

• 遵从语言习惯

  这条简单的建议将确保你的读者可以明白你所编写的所有代码。他们做出的错误设想会更少。

• 检查数值的上下限

  即使是最基本的计算，也会使数值型变量上溢或下溢。对此要非常注意。语言规范或核心库提供了一些机制，用来确定各个标准类型的大小——别忘了使用这些机制。确保你了解所有可用的数值类型，以及每种类型最适合的情况。

  检查并确保每一次运算都是可靠稳定的。例如，确保自己一定不要使用可能会造成除0错误的值。

• 正确设置常量

  C或C++语言的程序员真的应该对常量的设置保持高度警惕，这会让日子好过很多。尽可能将所有可以设置成常量的都设为常量。这样做有两个好处：首先，常量的限制条件可以充当代码记录；其次，常量使编译器可以找到你所犯下的愚蠢错误。这样，你就可以避免修改超出上下限的数据了。